package com.javabasic.algorithm.leetcode;

import org.junit.Test;


import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/6/29 12:57
 * @Version 1.0
 **/
public class KthLargestElementInAnArray {
    // TODO 方法一：利用Map数据结构
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length, value;
        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < len; i++) {
            value = map.getOrDefault(nums[i], 0) + 1;
            map.put(nums[i], value);
        }
        if (k > len) return -1;
        Set<Integer> keys = map.keySet();
        System.out.println(len);
        int tag = 0, result = -1;
        for (Integer key : keys) {
            tag += map.get(key);

            if (tag >= len - k + 1) {
                System.out.println(key +"----"+ tag+"----"+map.get(key));
                result = key;
                break;
            }
        }
        return result;
    }

    @Test
    public void test() {
        int[] ints = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        Scanner cin = new Scanner(System.in);
//        int k = cin.nextInt();
        int k = 4;
        System.out.println(getIndexOfKNum(ints, 0, ints.length-1, ints.length-1+k));
    }

    // 3, 2, 3, 1, 2, 4, 5, 5, 6
    // 2, 2, 3, 1, 3, 4, 5, 5, 6

    public int getIndexOfKNum(int num[],int left, int right, int k) {
        if (left < right) {
            int tag = orderArray(num,left,right);
            System.out.println(tag);
            if (tag-left+1 > k) {
                return getIndexOfKNum(num,left,tag-1,k);
            } else if (tag-left+1 < k) {
                return getIndexOfKNum(num,tag+1,right,k-tag+left-1);
            } else {
                return num[tag];
            }
        } else if (right == left) {
            if (k == 1) {
                return num[right];
            }
        }
        System.out.println("left = " + left + " right = " + right);
        return -1;

    }

    private int orderArray(int[] num, int left, int right) {
        int i = left + 1, j = right, tagNum = num[left];

        while (i < j) {
            do{}while (num[i++] <= tagNum);
            do{}while (num[j--] > tagNum);
            if (i < j) {
                int temp = num[i];
                num[j] = num[i];
                num[j] = temp;
            }
        }
        int temp = num[j];
        num[left] = num[j];
        num[j] = tagNum;
        return j;
    }



    static Scanner cin = new Scanner(System.in);

    static Random random = new Random(100);
    public static void main(String[] args) {
        int array[] = new int[20];
        for (int i = 0; i < 10; i++) {
            System.out.println("排序前：");
            for (int j = 0; j < 20; j++) {
                array[j] = random.nextInt(100);
                System.out.print(array[j] + " ");
            }
            quickSort(array,0,array.length-1);
            System.out.println("\n排序后：");
            for (int j = 0; j < 20; j++) {
                System.out.print(array[j] + " ");
            }
            System.out.println("\n第10大得数：" + getKthNum(array, 0, array.length - 1, 10) + "\n");

        }
    }
    public static int findKthLargest2(int[] nums, int k) {
        return getKthNum(nums,0,nums.length-1,nums.length-k+1);
    }

    public static int getKthNum(int[] nums, int left, int right,int k) {
        if (left < right) {
            int tag = executeSort(nums,left,right);
            if (tag + 1 > k) {
                return getKthNum(nums,left,tag-1,k);
            } else if (tag + 1 < k) {
                return getKthNum(nums,tag+1, right,k);
            } else {
                return nums[tag];
            }
        } else if (left == right) {
            return nums[left];
        } else {
            return -1;
        }
    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int tag = executeSort(nums,left,right);
            quickSort(nums,left,tag-1);
            quickSort(nums,tag+1, right);
        }
    }

    private static int executeSort(int[] nums, int left, int right) {
        int tagNum = nums[left];
        while (left < right) {
            while (nums[right] > tagNum && right > left) {
                right--;
            }
            nums[left] = nums[right];
            while (nums[left] <= tagNum && right > left) {
                left++;
            }
            nums[right] = nums[left];
            nums[left] = tagNum;
        }
        return left;
    }
}
